<<<<<<< HEAD
#include "activitySelect.h"
#include "bucketsort.h"
#include "canJump.h"
#include "coinChange.h"
#include "countSort.h"
#include "decode.h"
#include "divide.h"
#include "findLengthOfLCIS.h"
#include "findMaxForm.h"
#include "findMaxSubarray.h"
#include "heap.h"
#include "isSubStructure.h"
#include "isValidBST.h"
#include "list.h"
#include "longestCommonSubsequence.h"
#include "matrix.h"
#include "maxDepth.h"
#include "maxSteelPrice.h"
#include "mirrorTree.h"
#include "sortedArrayToBST.h"
#include "utilTools.h"
#include "utils.h"
#include <bits/stdc++.h>
#include <iostream>
#include <utility>
#include "postorderTraversal.h"
#include "Node.h"
#include "preorder.h"
#include "levelOrderBottom.h"
#include "preorderTraversal.h"
#include "isBalanced.h"
#include "BFSTravel.h"
#include "levelOrder.h"
#include "movingCount.h"
using namespace std;
int main()
{
    int a = (numeric_limits<int>::min)();
    int b = (numeric_limits<int>::max)();
    TreeNode* root1 = new TreeNode(1);
    TreeNode* root11 = new TreeNode(2);
    TreeNode* root12 = new TreeNode(2);
    TreeNode* root13 = new TreeNode(3);
    TreeNode* root14 = new TreeNode(3);
    TreeNode* root15 = new TreeNode(4);
    root1->left=root11;
    root1->right=root12;
    root11->left = root13;
    root12->right = root14;
    root14->left = root15;
    // cout<<boolalpha<<isBalanced(root1)<<endl;
    // vector<vector<int>> res = levelOrder1(root1);
    // show_vector2(res);
    cout<<movingCount(2,3,1)<<endl;
    cout<<movingCount(3,1,0)<<endl;
    cout<<movingCount(1,2,1)<<endl;
    cout<<movingCount(38,15,9)<<endl;

    delete root1;
    delete root11;
    delete root12;
    delete root13;
    delete root14;
    delete root15;
    
    
    // cout << divide(10, 3) << endl;
    // cout << divide(100, 3) << endl;
    // cout << divide(-100, -2) << endl;
    // cout << divide(a, -1) << endl;
    // cout << divide(a, 1) << endl;
    // cout << divide(b, -1) << endl;
    // cout << divide(b, 1) << endl;
    // vector<pair<int,int>> data = {{1,4},{3,5},{0,6},{5,7},{3,9},{5,9},{6,10},{8,11},{8,12},{2,14},{12,16}};
    // cout<<activitySelect(data,0,data.size());
    // vector<int> nums1 = {2,3,1,1,4};
    // vector<int> nums2 = {3,2,1,0,4};
    // vector<int> nums3 = {1};
    // vector<int> nums4 = {0,1,2};
    // cout<<boolalpha<<canJump(nums1)<<endl;
    // cout<<boolalpha<<canJump(nums2)<<endl;
    // cout<<boolalpha<<canJump(nums3)<<endl;
    // cout<<boolalpha<<canJump(nums4)<<endl;
    // vector<string> strs = {"10", "0001", "111001", "1", "0"};
    // int m = 5, n = 3;
    // cout << findMaxForm1(strs, m, n);
    // // cout<<longestCommonSubsequence("uvirivwbkdijstyjgdahmtutav","apazcdspcnolsvmlorqxazglyjq")<<endl;
    // vector<int> data = {1, 2, 3};
    // int first = 1;
    // // Matrix2D<int> m = {{1, 2, 3, 4, 5, 6, 7, 8, 9}, 3, 3};
    // cout << m << endl;
    // int N = 10;
    // List<int> list = List<int>(N);
    // list.append(8);
    // list.append(9);
    // cout << "输出当前的顺序表:" << endl;
    // list.show();
    // list.insert(1, 10);
    // cout << "插入元素后输出当前的顺序表:" << endl;
    // list.show();
    // // list.remove(1);
    // list.setValue(1, 11);
    // cout << "设置第二个元素为11后" << endl;
    // list.show();
    // cout << "显示11所在位置" << endl;
    // cout << list.getPos(11) << endl;
    // cout << "显示最终的变量" << endl;
    // list.show();
    // cout << "删除第1个元素" << endl;
    // list.remove(0);
    // list.remove(0);
    // list.remove(0);
    // list.show();
    // cout << "长度为:" << list.getLen() << endl;
}

//// 判断一个点是否在矩形中
// bool point_in_area(int x, int y, Rect &r) {
//    return (x > r.m_x && y > r.m_y && x < (r.m_x + r.m_w) && y < (r.m_y +
//    r.m_h));
//}
//
//
// bool isOverlap(Rect &rect1, Rect &rect2) {
//    int lefttop_x1 = rect1.m_x;
//    int lefttop_y1 = rect1.m_y;//rect1的左上角
//    int rightbotton_x1 = lefttop_x1 + rect1.m_w;
//    int rightbotton_y1 = lefttop_y1 + rect1.m_h;//rect2的右下角
//
//    int lefttop_x2 = rect2.m_x;
//    int lefttop_y2 = rect2.m_y;//rect2的左上角
//    int rightbotton_x2 = lefttop_x2 + rect2.m_w;
//    int rightbotton_y2 = lefttop_y2 + rect2.m_h;//rect2的右下角
//    bool res = (lefttop_y1 >= rightbotton_y2) || (lefttop_y2 >=
//    rightbotton_y1) || (rightbotton_x2 <= lefttop_x1) ||
//               (lefttop_x2 >= rightbotton_x1);// 上下左右
//    return !res;
//}
//
// double IOU(Rect &r1, Rect &r2) {
//    double iou = 0;
//    if (!isOverlap(r1, r2)) {
//        return iou;
//    } else {
//        int x1 = std::max(r1.m_x, r2.m_x);
//        int y1 = std::max(r1.m_y, r2.m_y);// 相交矩形区域的左上角坐标
//        int x2 = std::min(r1.m_x + r1.m_w, r2.m_x + r2.m_w);
//        int y2 = std::min(r1.m_y + r1.m_h, r2.m_y +
//        r2.m_h);//相交矩形区域的右下角坐标 int w = x2 - x1; int h = y2 - y1;
//        double insert_area = h * w;
//        iou = insert_area / (r1.area() + r2.area() - insert_area);
//        return (iou > 0) ? iou : 0;;
//    }
//}
//
// bool isRect(Rect &r) {
//    return r.m_h >= 0 && r.m_y >= 0 && r.m_h > 0 && r.m_w > 0;
//}
//
// bool cmp(pair<int, double> a, pair<int, double> b) {
//    return a.second > b.second;
//}
//
// void show_rect(Rect &current, double score) {
//    cout << "Current Rec x " << current.m_x << " y:" << current.m_y << " " <<
//    score << " ";
//}
//
// vector<Rect> nms(vector<Rect> &proposals, const double nms_threshold,
// vector<pair<int, double>> &scores) {
//    // 从大到小排序得分
//    sort(scores.begin(), scores.end(), cmp);
//    // 标记矩形框是否被删除
//    vector<bool> isDel(scores.size(), false);
//    vector<Rect> new_proposals;
//    for (int i = 0; i < scores.size(); i++) {
//        int best_index = scores[i].first; // 最高得分的rect的索引
//        if (!isDel[best_index]) {
//            Rect best_rect = proposals[best_index];
//            for (int other_index = i + 1; other_index < scores.size();
//            other_index++) {//非最高得分的其他rect
//
//                Rect choose = proposals[scores[other_index].first];
//                if (!isDel[other_index]) {
//                    double iou = IOU(choose, best_rect);
//                    cout << "Best Rect:" << best_rect.m_x << " " <<
//                    best_rect.m_y << " " << best_rect.m_w << " "
//                         << best_rect.m_h
//                         << " <=====> " << proposals[other_index].m_x << " "
//                         << proposals[other_index].m_y
//                         << " " << proposals[other_index].m_w << " " <<
//                         proposals[other_index].m_h << " IOU =" << iou
//                         << "\n";
//                    if (iou > nms_threshold)
//                        isDel[scores[other_index].first] =
//                        true;//标记删除iou超过阈值的rect的index
//                }
//
//            }
//            if (!isDel[best_index]) {
//                new_proposals.push_back(best_rect);
//                isDel[best_index] = true;
//            }
//        } else
//            continue;
//
//    }
//    return new_proposals;
//}
//
//
// int main() {
//    Rect r1 = Rect(0, 0, 20, 30);
//    Rect r2 = Rect(5, 5, 30, 40);
//    Rect r3 = Rect(30, 0, 20, 10);
//    Rect r4 = Rect(30, 35, 10, 15);
//    vector<pair<int, double>> scores = {{0, 0.9},
//                                        {1, 0.6},
//                                        {2, 0.4},
//                                        {3, 0.99}};
//    vector<Rect> origin = {r1, r2, r3, r4};
//    vector<Rect> propos;
//    for (auto e:origin) {
//        if (isRect(e))
//            propos.push_back(e);
//    }
//    vector<Rect> res = nms(propos, 0.25, scores);
//    for (auto e:res) {
//        cout << "Rect " << e.area() << endl;
//    }
//}
//
////    sort(a.begin(), a.end(), cmp);
////    for (auto e:a) {
////        cout << "first:" << e.first << " " << e.second << endl;
////    }
////}
//

////int main() {
////  //    int vexNum = 6;
////  //    vector<vector<int>>graph(vexNum+1,vector<int>(vexNum+1,INT_MAX));
////  //    graph[1][2] = 2;
////  //    graph[1][3] = 1;
////  //
////  //    graph[2][3] = 4;
////  //    graph[2][5] = 3;
////  //    graph[3][4] = 6;
////  //    graph[4][5] = 1;
////  //    graph[4][6] = 2;
////  //    graph[5][6] = 1;
////  //    vector<int>nums = {1,2,3};
////  //    vector<vector<int>>res = permute(nums);
////  //    for(auto e:res){
////  //        show_vector(e);
////  //    }
//////  vector<int> node_edge1 = {7, 9, 14};
//////  vector<int> node_edge2 = {7, 10, 15};
//////  vector<int> node_edge3 = {2, 9, 11};
//////  vector<int> node_edge4 = {15, 11, 6};
//////  vector<int> node_edge5 = {6, 4};
//////  vector<int> node_edge6 = {2, 9, 14};
//////
//////  GraphNode *node1 = new GraphNode("1", node_edge1);
//////  GraphNode *node2 = new GraphNode("2", node_edge2);
//////  GraphNode *node3 = new GraphNode("3", node_edge3);
//////  GraphNode *node4 = new GraphNode("4", node_edge4);
//////  GraphNode *node5 = new GraphNode("5", node_edge5);
//////  GraphNode *node6 = new GraphNode("6", node_edge6);
//////
//////  map<int, GraphNode *> adj1 = {{7, node2}, {9, node3}, {14, node6}};
//////  map<int, GraphNode *> adj2 = {{7, node1}, {10, node3}, {15, node6}};
//////  map<int, GraphNode *> adj3 = {{2, node6}, {9, node1}, {11, node4}};
//////  map<int, GraphNode *> adj4 = {{6, node5}, {11, node3}, {15, node2}};
//////  map<int, GraphNode *> adj5 = {{4, node6}, {6, node4}};
//////  map<int, GraphNode *> adj6 = {{2, node3}, {9, node5}, {14, node1}};
//////
//////  node1->setEdgeToNode(adj1);
//////  node2->setEdgeToNode(adj2);
//////  node3->setEdgeToNode(adj3);
//////  node4->setEdgeToNode(adj4);
////  node5->setEdgeToNode(adj5);
//////  node6->setEdgeToNode(adj6);
//////  vector<string> result = dijkstra(node1, node5);
////
////  //    graph[6][6]=0;
////  //    Dplongestpath(graph);//DAG最长路径
////
////
////  return 0;
////}
=======
#include <iostream>
#include <limits>

#include "algorithm/common/include/activitySelect.h"
#include "algorithm/datastruct/include/TreeNode.h"
#include "algorithm/datastruct/include/TreeOperator.h"
using namespace std;
int main() {

    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);
    node1->left = node2;
    node1->right = node3;
    std::cout << maxPathSum(node1);
    delete node1;
    delete node2;
    delete node3;
}
// int main()
// {
// //    int a = (numeric_limits<int>::min)();
// //    int b = (numeric_limits<int>::max)();
// //    TreeNode* root1 = new TreeNode(1);
// //    TreeNode* root11 = new TreeNode(2);
// //    TreeNode* root12 = new TreeNode(2);
// //    TreeNode* root13 = new TreeNode(3);
// //    TreeNode* root14 = new TreeNode(3);
// //    TreeNode* root15 = new TreeNode(4);
// //    root1->left=root11;
// //    root1->right=root12;
// //    root11->left = root13;
// //    root12->right = root14;
// //    root14->left = root15;
// //    // cout<<boolalpha<<isBalanced(root1)<<endl;
// //    // vector<vector<int>> res = levelOrder1(root1);
// //    // show_vector2(res);
//     cout<<movingCount(2,3,1)<<endl;
//     cout<<movingCount(3,1,0)<<endl;
//     cout<<movingCount(1,2,1)<<endl;
//     cout<<movingCount(38,15,9)<<endl;
//
// //    delete root1;
// //    delete root11;
// //    delete root12;
// //    delete root13;
// //    delete root14;
// //    delete root15;
//
//
//     // cout << divide(10, 3) << endl;
//     // cout << divide(100, 3) << endl;
//     // cout << divide(-100, -2) << endl;
//     // cout << divide(a, -1) << endl;
//     // cout << divide(a, 1) << endl;
//     // cout << divide(b, -1) << endl;
//     // cout << divide(b, 1) << endl;
//     // vector<pair<int,int>> data =
//     {{1,4},{3,5},{0,6},{5,7},{3,9},{5,9},{6,10},{8,11},{8,12},{2,14},{12,16}};
//     // cout<<activitySelect(data,0,data.size());
//     // vector<int> nums1 = {2,3,1,1,4};
//     // vector<int> nums2 = {3,2,1,0,4};
//     // vector<int> nums3 = {1};
//     // vector<int> nums4 = {0,1,2};
//     // cout<<boolalpha<<canJump(nums1)<<endl;
//     // cout<<boolalpha<<canJump(nums2)<<endl;
//     // cout<<boolalpha<<canJump(nums3)<<endl;
//     // cout<<boolalpha<<canJump(nums4)<<endl;
//     // vector<string> strs = {"10", "0001", "111001", "1", "0"};
//     // int m = 5, n = 3;
//     // cout << findMaxForm1(strs, m, n);
//     // //
//     cout<<longestCommonSubsequence("uvirivwbkdijstyjgdahmtutav","apazcdspcnolsvmlorqxazglyjq")<<endl;
//     // vector<int> data = {1, 2, 3};
//     // int first = 1;
//     // // Matrix2D<int> m = {{1, 2, 3, 4, 5, 6, 7, 8, 9}, 3, 3};
//     // cout << m << endl;
//     // int N = 10;
//     // List<int> list = List<int>(N);
//     // list.append(8);
//     // list.append(9);
//     // cout << "输出当前的顺序表:" << endl;
//     // list.show();
//     // list.insert(1, 10);
//     // cout << "插入元素后输出当前的顺序表:" << endl;
//     // list.show();
//     // // list.remove(1);
//     // list.setValue(1, 11);
//     // cout << "设置第二个元素为11后" << endl;
//     // list.show();
//     // cout << "显示11所在位置" << endl;
//     // cout << list.getPos(11) << endl;
//     // cout << "显示最终的变量" << endl;
//     // list.show();
//     // cout << "删除第1个元素" << endl;
//     // list.remove(0);
//     // list.remove(0);
//     // list.remove(0);
//     // list.show();
//     // cout << "长度为:" << list.getLen() << endl;
// }
//
// //// 判断一个点是否在矩形中
// // bool point_in_area(int x, int y, Rect &r) {
// //    return (x > r.m_x && y > r.m_y && x < (r.m_x + r.m_w) && y < (r.m_y +
// //    r.m_h));
// //}
// //
// //
// // bool isOverlap(Rect &rect1, Rect &rect2) {
// //    int lefttop_x1 = rect1.m_x;
// //    int lefttop_y1 = rect1.m_y;//rect1的左上角
// //    int rightbotton_x1 = lefttop_x1 + rect1.m_w;
// //    int rightbotton_y1 = lefttop_y1 + rect1.m_h;//rect2的右下角
// //
// //    int lefttop_x2 = rect2.m_x;
// //    int lefttop_y2 = rect2.m_y;//rect2的左上角
// //    int rightbotton_x2 = lefttop_x2 + rect2.m_w;
// //    int rightbotton_y2 = lefttop_y2 + rect2.m_h;//rect2的右下角
// //    bool res = (lefttop_y1 >= rightbotton_y2) || (lefttop_y2 >=
// //    rightbotton_y1) || (rightbotton_x2 <= lefttop_x1) ||
// //               (lefttop_x2 >= rightbotton_x1);// 上下左右
// //    return !res;
// //}
// //
// // double IOU(Rect &r1, Rect &r2) {
// //    double iou = 0;
// //    if (!isOverlap(r1, r2)) {
// //        return iou;
// //    } else {
// //        int x1 = std::max(r1.m_x, r2.m_x);
// //        int y1 = std::max(r1.m_y, r2.m_y);// 相交矩形区域的左上角坐标
// //        int x2 = std::min(r1.m_x + r1.m_w, r2.m_x + r2.m_w);
// //        int y2 = std::min(r1.m_y + r1.m_h, r2.m_y +
// //        r2.m_h);//相交矩形区域的右下角坐标 int w = x2 - x1; int h = y2 -
// y1;
// //        double insert_area = h * w;
// //        iou = insert_area / (r1.area() + r2.area() - insert_area);
// //        return (iou > 0) ? iou : 0;;
// //    }
// //}
// //
// // bool isRect(Rect &r) {
// //    return r.m_h >= 0 && r.m_y >= 0 && r.m_h > 0 && r.m_w > 0;
// //}
// //
// // bool cmp(pair<int, double> a, pair<int, double> b) {
// //    return a.second > b.second;
// //}
// //
// // void show_rect(Rect &current, double score) {
// //    cout << "Current Rec x " << current.m_x << " y:" << current.m_y << " "
// <<
// //    score << " ";
// //}
// //
// // vector<Rect> nms(vector<Rect> &proposals, const double nms_threshold,
// // vector<pair<int, double>> &scores) {
// //    // 从大到小排序得分
// //    sort(scores.begin(), scores.end(), cmp);
// //    // 标记矩形框是否被删除
// //    vector<bool> isDel(scores.size(), false);
// //    vector<Rect> new_proposals;
// //    for (int i = 0; i < scores.size(); i++) {
// //        int best_index = scores[i].first; // 最高得分的rect的索引
// //        if (!isDel[best_index]) {
// //            Rect best_rect = proposals[best_index];
// //            for (int other_index = i + 1; other_index < scores.size();
// //            other_index++) {//非最高得分的其他rect
// //
// //                Rect choose = proposals[scores[other_index].first];
// //                if (!isDel[other_index]) {
// //                    double iou = IOU(choose, best_rect);
// //                    cout << "Best Rect:" << best_rect.m_x << " " <<
// //                    best_rect.m_y << " " << best_rect.m_w << " "
// //                         << best_rect.m_h
// //                         << " <=====> " << proposals[other_index].m_x << "
// "
// //                         << proposals[other_index].m_y
// //                         << " " << proposals[other_index].m_w << " " <<
// //                         proposals[other_index].m_h << " IOU =" << iou
// //                         << "\n";
// //                    if (iou > nms_threshold)
// //                        isDel[scores[other_index].first] =
// //                        true;//标记删除iou超过阈值的rect的index
// //                }
// //
// //            }
// //            if (!isDel[best_index]) {
// //                new_proposals.push_back(best_rect);
// //                isDel[best_index] = true;
// //            }
// //        } else
// //            continue;
// //
// //    }
// //    return new_proposals;
// //}
// //
// //
// // int main() {
// //    Rect r1 = Rect(0, 0, 20, 30);
// //    Rect r2 = Rect(5, 5, 30, 40);
// //    Rect r3 = Rect(30, 0, 20, 10);
// //    Rect r4 = Rect(30, 35, 10, 15);
// //    vector<pair<int, double>> scores = {{0, 0.9},
// //                                        {1, 0.6},
// //                                        {2, 0.4},
// //                                        {3, 0.99}};
// //    vector<Rect> origin = {r1, r2, r3, r4};
// //    vector<Rect> propos;
// //    for (auto e:origin) {
// //        if (isRect(e))
// //            propos.push_back(e);
// //    }
// //    vector<Rect> res = nms(propos, 0.25, scores);
// //    for (auto e:res) {
// //        cout << "Rect " << e.area() << endl;
// //    }
// //}
// //
// ////    sort(a.begin(), a.end(), cmp);
// ////    for (auto e:a) {
// ////        cout << "first:" << e.first << " " << e.second << endl;
// ////    }
// ////}
// //
//
// ////int main() {
// ////  //    int vexNum = 6;
// ////  //    vector<vector<int>>graph(vexNum+1,vector<int>(vexNum+1,INT_MAX));
// ////  //    graph[1][2] = 2;
// ////  //    graph[1][3] = 1;
// ////  //
// ////  //    graph[2][3] = 4;
// ////  //    graph[2][5] = 3;
// ////  //    graph[3][4] = 6;
// ////  //    graph[4][5] = 1;
// ////  //    graph[4][6] = 2;
// ////  //    graph[5][6] = 1;
// ////  //    vector<int>nums = {1,2,3};
// ////  //    vector<vector<int>>res = permute(nums);
// ////  //    for(auto e:res){
// ////  //        show_vector(e);
// ////  //    }
// //////  vector<int> node_edge1 = {7, 9, 14};
// //////  vector<int> node_edge2 = {7, 10, 15};
// //////  vector<int> node_edge3 = {2, 9, 11};
// //////  vector<int> node_edge4 = {15, 11, 6};
// //////  vector<int> node_edge5 = {6, 4};
// //////  vector<int> node_edge6 = {2, 9, 14};
// //////
// //////  GraphNode *node1 = new GraphNode("1", node_edge1);
// //////  GraphNode *node2 = new GraphNode("2", node_edge2);
// //////  GraphNode *node3 = new GraphNode("3", node_edge3);
// //////  GraphNode *node4 = new GraphNode("4", node_edge4);
// //////  GraphNode *node5 = new GraphNode("5", node_edge5);
// //////  GraphNode *node6 = new GraphNode("6", node_edge6);
// //////
// //////  map<int, GraphNode *> adj1 = {{7, node2}, {9, node3}, {14, node6}};
// //////  map<int, GraphNode *> adj2 = {{7, node1}, {10, node3}, {15, node6}};
// //////  map<int, GraphNode *> adj3 = {{2, node6}, {9, node1}, {11, node4}};
// //////  map<int, GraphNode *> adj4 = {{6, node5}, {11, node3}, {15, node2}};
// //////  map<int, GraphNode *> adj5 = {{4, node6}, {6, node4}};
// //////  map<int, GraphNode *> adj6 = {{2, node3}, {9, node5}, {14, node1}};
// //////
// //////  node1->setEdgeToNode(adj1);
// //////  node2->setEdgeToNode(adj2);
// //////  node3->setEdgeToNode(adj3);
// //////  node4->setEdgeToNode(adj4);
// ////  node5->setEdgeToNode(adj5);
// //////  node6->setEdgeToNode(adj6);
// //////  vector<string> result = dijkstra(node1, node5);
// ////
// ////  //    graph[6][6]=0;
// ////  //    Dplongestpath(graph);//DAG最长路径
// ////
// ////
// ////  return 0;
// ////}
>>>>>>> dev
